// ------------------------------------------------------------------------------------------------
// ---- MENOR CAMINHO ENTRE TODOS OS PARES DE VERTICES --------------------------------------------
// ---- ALGORITMO DE FLOYD-WARSHALL ---------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <climits>
#include <cfloat>
#include <windows.h>
using namespace std;


typedef struct vertice {
    int grau;
    int* adjL;
    double* adjW;
} vertice;

typedef struct wdigraph {
	int N;// numero de vertices
	int M;// numero de arestas
	vertice* V;
} wdigraph;


// ----------------------------------------
// ALGORITMO DE FLOYD
// ----------------------------------------
void floyd(wdigraph& G);


// ---------------------------------------
// Manutenção de grafos
// ---------------------------------------
bool wdigraph_create(wdigraph& G);
void wdigraph_delete(wdigraph& G);

void imprime_matriz(int** d, int m, int n);
void imprime_matriz(double** d, int m, int n);


// ------------------------------------------------------------------------------------------------
// ------ MAIN ------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
int main() {
    int i,j,k;

    wdigraph G;
    if (!wdigraph_create(G)) return -1;


    // ALGORITMO DE FLOYD
    floyd(G);


    wdigraph_delete(G);
    return 0;
}

// ------------------------------------------------------------------------------------------------
// ---- ALGORITMO DE FLOYD ------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void floyd(wdigraph& G) {
    int i,j,k;
    int N = G.N;
    double** dist = new double*[N];
    double** pi = new double*[N];
    for (i=0; i<N; i++) {
        dist[i] = new double[N];
        pi[i] = new double[N];
        for (j=0; j<N; j++) {
            dist[i][j] = DBL_MAX;
            pi[i][j] = -1;
        }
        dist[i][i] = 0;
    }
    for (i=0; i<N; i++) {
        for (k=0; k<G.V[i].grau; k++) {
            j = G.V[i].adjL[k];
            dist[i][j] = G.V[i].adjW[k];
        }
    }
    imprime_matriz (dist,N,N);

    for (k=0; k<N; k++) {
        for (i=0; i<N; i++) {
            for (j=0; j<N; j++) {
                if (dist[i][j] > dist[i][k]+dist[k][j]) {
                    dist[i][j] = dist[i][k]+dist[k][j];
                    pi[i][j] = k;
                }
            }
        }
        imprime_matriz (dist,N,N);
    }

    for (i=0; i<N; i++) {
        delete[] dist[i];
        delete[] pi[i];
    }
    delete[] dist;
    delete[] pi;
}

// ------------------------------------------------------------------------------------------------
// ---- MANUTENÇÃO DE GRAFOS ----------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------


// ------------------------------------
// ------------------------------------
bool wdigraph_create(wdigraph& G) {
    G.N=0; G.M=0;
    G.V = NULL;

    ifstream arq;
    arq.open("entrada_floyd_adjL.txt");
    if (arq.fail()) return false;
    arq >> G.N;

    G.V = new vertice[G.N];
    for (int i=0; i<G.N; i++) {
        int grau;
        arq >> grau;
        G.V[i].grau = grau;
        G.M += grau;
        G.V[i].adjL = new int[grau];
        G.V[i].adjW = new double[grau];
        for (int k=0; k<grau; k++) {
            arq >> G.V[i].adjL[k];
            arq >> G.V[i].adjW[k];
        }
    }
    arq.close();
    return true;
}

// ------------------------------------
// ------------------------------------
void wdigraph_delete(wdigraph& G) {
    for (int i=0; i<G.N; i++) {
        if (G.V[i].adjL != NULL) delete[] G.V[i].adjL;
        if (G.V[i].adjW != NULL) delete[] G.V[i].adjW;
        G.V[i].adjL = NULL;
        G.V[i].adjW = NULL;
    }
    delete[] G.V;
    G.V = NULL;
}




// ------------------------------------
// ------------------------------------
void imprime_matriz(int** d, int m, int n) {
    int i,j;
    cout<<endl;
    for (i=0; i<m; i++) {
        for (j=0; j<n; j++) {
            if (d[i][j]<INT_MAX)
                cout<<d[i][j]<<" ";
            else
                cout<<"INF ";
        }
        cout<<endl;
    }
}
void imprime_matriz(double** d, int m, int n) {
    int i,j;
    cout<<endl;
    for (i=0; i<m; i++) {
        for (j=0; j<n; j++) {
            if (d[i][j]<DBL_MAX)
                cout<<d[i][j]<<" ";
            else
                cout<<"INF ";
        }
        cout<<endl;
    }
}